#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        # 使用矩阵可以. 但是也可以使用滚动数组节省空间, 并且省去了初始化矩阵的麻烦.

        # method1 : 可以按行计算
        rows, cols = len(obstacleGrid), len(obstacleGrid[0])

        paths = [0] * cols
        if obstacleGrid[0][0] == 1:
            return 0

        paths[0] = 1
        for row in range(0, rows):
            for col in range(0, cols):
                if obstacleGrid[row][col] == 1:
                    paths[col] = 0
                elif col == 0:
                    paths[col] = paths[col]
                    print('col %s' % paths[col])
                else:
                    paths[col] = paths[col] + paths[col-1]

        return paths[-1]


def main():
    print("start main")
    s = Solution()
    # ret = s.uniquePaths(3, 3)
    # ret = s.uniquePaths(2, 2)
    # ret = s.uniquePaths(4, 4)
    ret = s.uniquePathsWithObstacles([
        [0,0],
        [0,0],
        [0,0],
        [1,0],
        [0,0]
    ])

    print(ret)

if __name__ == "__main__":
    main()
